package 蓝桥杯十二;
import java.util.List;
import java.util.Map.Entry;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
/**
 * 这个 之后 在优化  一下 :
 * 
 *
 */
public class E最短路径 {
	public static void main(String []args) {
		Graph graph  = generator(2021);
//		System.out.println(graph.nodes.get(2021));
//		System.out.println(graph.nodes.get(2));
//		System.out.println(graph.nodes.size());
//		System.out.println(graph.nodes.get(1).nexts);
		long t1 = System.currentTimeMillis();
		HashMap<Node, Integer> disMap = dis(graph.nodes.get(1));
		System.out.println(disMap.get(graph.nodes.get(2021)));
		long t2 = System.currentTimeMillis();
		System.out.println(t2  - t1);
	}
	/**
	 * 这里 的 dis  函数 加不加 参数   根据 题 意 的具体 要求 明白  是什么 意思 吧
	 * @return
	 */
	public  static HashMap<Node,Integer> dis(Node root){
		HashMap<Node,Integer> disMap = new HashMap<>();
		HashSet<Node> selectedNode  = new HashSet<>();
		disMap.put(root, 0);
		Node minNode= getMinNode(disMap,selectedNode);
		while(minNode != null) {
			int distance = disMap.get(minNode);
			for(Edge e : minNode.edges) {
				if(!disMap.containsKey(e.to)) {
					disMap.put(e.to,distance + e.weight);
				}
				else
					disMap.put(e.to,Math.min(disMap.get(e.to), distance + e.weight));
			}
			/**
			 * 上面这个 for 循环   执行  之后  那么 minNode 所有的 邻接点 就处理 完了 那就  把minNode 锁死
			 * 怎么 锁死 不就是 直接 假如 到 selectedNode  
			 */
			selectedNode.add(minNode);
			minNode = getMinNode(disMap,selectedNode);
		}
		return disMap;
	}
	public static Node getMinNode(HashMap<Node,Integer> disMap,HashSet<Node> selectedNode) {
		Node minNode = null;
		int distance = Integer.MAX_VALUE;
		/**
		 * 无论 这种 写法  还是  下面这种 写法 都是 一种暴力的 写法  而不是 什么 高效 的方法
		 * 全是 遍历 查找 找出 minNode 很慢 
		 * 可以 用 堆 优化 
		 * (但是 又不能  用 系统的 堆 只能  自己 去改写 一下 堆 
		 * 为啥   因为  
		 *   个人 认为 : 这种 建图的 方式 是 全部 都是 使用 class 节点   来 创建的 
		 *   value 知识 class 中的 一个 属性   
		 *   反正 有点 抽象                  )
		 * 我在想 这样 一个 问题 
		 * 假如 用 链式 前向星的 形式 来 创建 图的   话 那样 会不会 可以 直接 用
		 * 系统的堆 优化 了 应该 是 这样 我感觉 
		 * 等到 后面 尝试 一下 
		 * 深入 学习的 时候自然 就会明白
		 *  
		 * 
		for(Entry<Node,Integer> entry : disMap.entrySet()) {
			Node node = entry.getKey();
			int dis  = entry.getValue();
			if(!selectedNode.contains(node) && dis < distance) {
				minNode = node;
				distance = dis;
			}
		}
		*/
		
		for(Node node : disMap.keySet()) {
			if(! selectedNode.contains(node) &&distance > disMap.get(node)) {
				distance  = disMap.get(node);
				minNode = node;
			}
		}
		return minNode;
	}
	public static Graph generator(int n) {
		Graph graph = new Graph();
		/**
		 * 			  仔细 去想一下 下面的代码    就是  枚举 呗
		 * Math.min(i+21, n);
		 * 这句 代码  就是 防止越界 呗  
		 * 	if(!graph.nodes.containsKey(from)) {
				graph.nodes.put(from, new Node(from));
			}
			if(!graph.nodes.containsKey(to)) {
				graph.nodes.put(to, new Node(to));
			}
			这些 代码 就用不到了 直接 不用 写 
			这种 是用来  判断   martix[][]  这种二维 数组 的 时候 
			这种 输入 边的 时候  实惠输入 两个 相同的点的 
			比如 [1,2,5][1,4,6]
		 */
		HashMap<Integer,Node> nodes = graph.nodes;
		for(int i = 1; i <= n;i++ ) {
			if(!nodes.containsKey(i)) {				
				Node from = new Node(i);
				graph.nodes.put(i,from);
			}
			for(int j = i + 1;j <= Math.min(i+21, n);j++) {
				int min = i *  j/gcd(i,j);
				if(!nodes.containsKey(j)) {
					Node to  = new Node(j);
					graph.nodes.put(j,to);
					
				}
				Node from = nodes.get(i);
				Node to = nodes.get(j);
				from.nexts.add(to);
				to.nexts.add(from);
				Edge e1 = new Edge(min,nodes.get(i),nodes.get(j));
				Edge e2 = new Edge(min,nodes.get(j),nodes.get(i));
//				node
				from.edges.add(e1);
				to.edges.add(e2);
				graph.edges.add(e1);
				graph.edges.add(e2);
			}
		}
		return graph;
	}
	public static int gcd(int a,int b) {
		return b == 0 ? a : gcd(b,a % b);
	}
}
class Graph{
	HashMap<Integer,Node> nodes;
	HashSet<Edge> edges;
	public Graph() {
		nodes = new HashMap<>();
		edges = new HashSet<>(); 
	}
}
class Node{
	/**
	 * 这个  题 入度 和 出度 就用不到  那还写 干嘛
	 * 入度 和出度 是 在点 上的 
	 */
	int value;
	List<Node> nexts;
//	List<Edge> edges;
//	  这里需不需要 定义 边 集 Edge 的 集合 会用到 吧  用的 到 dj特斯拉的 时候 就会 用到 这里 
	List<Edge> edges ;
	public Node(int value) {
		this.value = value;
		nexts = new ArrayList<>();
//		edges = new HashSet<>();
		edges = new ArrayList<>();
	}
	public String toString() {
		return "value "+ value;
	}
}
class Edge{
	int weight;
	Node from;
	Node to;
	public Edge(int weight,Node from,Node to) {
		this.weight = weight;
		this.from = from;
		this.to = to;
	}
}